/*
 * 静态链表-游标实现法
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define LISTSIZE 100


/* type */
struct Student {
    int id;
    char name[100];
    int age;
    char sex;
};
typedef struct Student ElemType;
//typedef int ElemType;


/*
 *
 */
struct static_node {
    ElemType data;
    int cur;        /* cursor, 0 point to nothing */
};
typedef struct static_node static_list_t;



void init_static_list(static_list_t list[]);
int  get_static_list_length(static_list_t list[]);
void delete_static_list(static_list_t list[]);
int  malloc_static_list(static_list_t list[]);
void free_static_list(static_list_t list[], int i);
int  insert_static_list(static_list_t list[], int pos, ElemType *item);
int  insert_static_list_head(static_list_t list[], ElemType *item);
int  insert_static_list_tail(static_list_t list[], ElemType *item);
int  delete_static_list_item(static_list_t list[], int pos, ElemType *item);
int  get_static_list_item(static_list_t list[], int pos, ElemType *item);
int  find_static_list_item(static_list_t list[], ElemType *item);
void trave_static_list(static_list_t list[], void (*print_info)(int n, ElemType *item));


void
print_student_info(int n, ElemType *stu)
{
    printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", n, stu->id, stu->name);
}




int
main(int argc, char *argv[])
{
    static_list_t list[LISTSIZE];
    int i, n;
    ElemType item;


    init_static_list(list);
    printf("static list length = %d\n", get_static_list_length(list));


    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        insert_static_list(list, i+1, &item);
    }

    /* 在第5个位置插入一个节点 (新插入节点排在第5位) */
    memset(&item, 0, sizeof(item));
    item.id = 11;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list(list, 5, &item);

    /* 在最后1个位置后插入一个节点 (新插入节点排在第12位) */
    memset(&item, 0, sizeof(item));
    item.id = 12;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    n = get_static_list_length(list);
    insert_static_list(list, n+1, &item);


    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_static_list(list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_static_list(list, -1, &item));


    printf("\n");
    n = get_static_list_length(list);
    printf("After insert: n=[%d]\n", n);
    for (i = 0; i < n; ++i) {
        memset(&item, 0, sizeof(item));
        get_static_list_item(list, i+1, &item); /* 应该要实现一个遍历链表的函数，而不是调用获取指定位置元素的函数 */
        printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", i+1, item.id, item.name);
    }




    /* 头插法 */
    memset(&item, 0, sizeof(item));
    item.id = 13;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list_head(list, &item);

    memset(&item, 0, sizeof(item));
    item.id = 14;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list_head(list, &item);


    /* 尾插法 */
    memset(&item, 0, sizeof(item));
    item.id = 15;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list_tail(list, &item);

    memset(&item, 0, sizeof(item));
    item.id = 16;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list_tail(list, &item);


    printf("\n");
    n = get_static_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_static_list(list, print_student_info);




    printf("\n");
    /* 删除第一个元素 */
    delete_static_list_item(list, 1, NULL);

    /* 删除最后一个元素 */
    n = get_static_list_length(list);
    delete_static_list_item(list, n, NULL);

    /* 删除第3个元素 */
    memset(&item, 0, sizeof(item));
    delete_static_list_item(list, 3, &item);
    printf("删除第3个元素: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);

    /* 删除第一个元素 */
    delete_static_list_item(list, 1, NULL);

    /* 删除最后一个元素 */
    n = get_static_list_length(list);
    delete_static_list_item(list, n, NULL);

    printf("\n");
    n = get_static_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_static_list(list, print_student_info);




    /* 查找元素， 对比函数应该也是使用回调函数才正确，由使用者传入 */
    printf("\n");
    memset(&item, 0, sizeof(item));
    item.id = 7;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_static_list_item(list, &item))
        printf("元素[%d]能找到, pos[%d]\n", item.id, n);
    else
        printf("元素[%d]不能找到\n", item.id);

    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_static_list_item(list, &item))
        printf("元素[%d]能找到, pos[%d]\n", item.id, n);
    else
        printf("元素[%d]不能找到\n", item.id);


    printf("删除链表前，元素个数[%d]\n", get_static_list_length(list));
    delete_static_list(list);
    delete_static_list(list);
    printf("删除链表后，元素个数[%d]\n", get_static_list_length(list));


    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_static_list(list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_static_list(list, -1, &item));
    


    /* 空链表插入第一个节点 */
    memset(&item, 0, sizeof(item));
    item.id = 1;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list(list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 2;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list(list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 3;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list(list, 1, &item);

    /* 在第2个位置插入一个节点 (新插入节点排在第2位) */
    memset(&item, 0, sizeof(item));
    item.id = 4;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_static_list(list, 2, &item);


    printf("\n");
    n = get_static_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_static_list(list, print_student_info);

    printf("删除链表前，元素个数[%d]\n", get_static_list_length(list));
    delete_static_list(list);
    printf("删除链表后，元素个数[%d]\n", get_static_list_length(list));




    return 0;
}



/******************************************************************************/



/*
 * 初始化静态链表
 *
length: n

index    0    1    2    3              n-3   n-2  n-1
        +----+----+----+----+         +-----+----+----+
data    |    |    |    |    |         |     |    |    |
        +----+----+----+----+ ... ... +-----+----+----+
cur     | 1  | 2  | 3  | 4  |         | n-2 | 0  | 0  |
        +----+----+----+----+         +-----+----+----+

 *
 * 数组0的游标cur存放下一个可插入元素的数组下标，
 * 数组0的data不存放数据
 * 未被使用的数组元素称为备用链表
 *
 * 接着从1 ~ n-1的data存放数据，
 * 数组1的游标cur存放下一个结点的下标，即数组2，以此类推
 *
 * 最后一个数组的游标存放第一个插入元素的数组下标，即作为头结点，如果游标为0，
 * 即链表为空。data不存放数据
 */
void
init_static_list(static_list_t list[])
{
    int i;

    memset(list, 0, sizeof(static_list_t)*LISTSIZE);

    /* [0, N-1) */
    for (i = 0; i < LISTSIZE - 1; ++i)
        list[i].cur = i + 1;

    /* 最后两个数组的游标设为0 */
    list[i - 1].cur = 0;
    list[LISTSIZE - 1].cur = 0;
}

/*
 * 返回静态链表的个数
 */
int
get_static_list_length(static_list_t list[])
{
    int n, i;

    /* the last array index, which point to the first item */
    i = LISTSIZE - 1;

    n = 0;
    while ((i = list[i].cur) != 0) {
        ++n;
        //printf("list[%d].cur = %d\n", i, list[i].cur);
    }

    return n;
}

/*
 * 清空静态表
 */
void
delete_static_list(static_list_t list[])
{
    init_static_list(list);
}



/*
 * 申请静态链表下一个空的数组序号
 * 从备用链表获取可分配的节点下标
 */
int
malloc_static_list(static_list_t list[])
{
    int i;

    /* 数组0的游标cur存放下一个可插入元素的数组下标 */
    i = list[0].cur;

    if (list[0].cur)
        list[0].cur = list[i].cur;

    return i;
}

/*
 * 释放静态链表所占用的某个数组序号
 * 把空闲节点回收到备用链表
 */
void
free_static_list(static_list_t list[], int i)
{
    list[i].cur = list[0].cur;
    list[0].cur = i;
}

/*
 * 在静态链表的第i个位置插入元素
 *
 * 插入算法的思路
 *
 * pos的范围是 [1, length+1]
 *
 */
int
insert_static_list(static_list_t list[], int pos, ElemType *item)
{
    int i, j, k;

    /* 指向最后一个元素的下标, 从而获取第一个元素的位置 */
    k = LISTSIZE - 1;

    /* 判断pos的位置 */
    if (pos < 1 || pos > get_static_list_length(list) + 1)
        return -1;

    /* 获取下一个空闲位置的下标 */
    i = malloc_static_list(list);

    if (i) {
        memcpy(&list[i].data, item, sizeof(ElemType));

        /* 找到插入元素之前的位置 */
        for (j = 1; j <= pos - 1; ++j)
            k = list[k].cur;

        list[i].cur = list[k].cur;
        list[k].cur = i;

        return 0;
    }

    return -2;
}

/*
 * 头插法
 */
int
insert_static_list_head(static_list_t list[], ElemType *item)
{
    int i, k;

    /* the last array index, which point to the first item */
    k = LISTSIZE - 1;

    /* 获取下一个空闲位置的下标 */
    i = malloc_static_list(list);

    if (i) {
        memcpy(&list[i].data, item, sizeof(ElemType));

        list[i].cur = list[k].cur;
        list[k].cur = i;

        return 0;
    }

    return -1;
}


/*
 * 尾插法
 */
int
insert_static_list_tail(static_list_t list[], ElemType *item)
{
    int i, k;

    /* the last array index, which point to the first item */
    k = LISTSIZE - 1;

    /* 获取下一个空闲位置的下标 */
    i = malloc_static_list(list);

    if (i) {
        memcpy(&list[i].data, item, sizeof(ElemType));

        /* 找到最后一个元素的位置*/
        while (list[k].cur != 0)
            k = list[k].cur;

        list[i].cur = list[k].cur;
        list[k].cur = i;

        return 0;
    }

    return -1;
}


/*
 * 在静态链表的删除第i个位置的元素
 *
 * 删除算法的思路:
 *
 * pos的范围是 [1, length]
 */
int
delete_static_list_item(static_list_t list[], int pos, ElemType *item)
{
    int j, k;

    /* 指向最后一个元素的下标, 从而获取第一个元素的位置 */
    k = LISTSIZE - 1;

    if (pos < 1 || pos > get_static_list_length(list))
        return -1;

    /* 找出删除元素的前一个元素 */
    for (j = 1; j <= pos - 1; ++j)
        k = list[k].cur;

    /* 获取删除元素的游标 */
    j = list[k].cur;

    if (item != NULL)
        memcpy(item, &list[j].data, sizeof(ElemType));

    list[k].cur = list[j].cur; /* 将删除元素的前一个元素的游标指向下一个元素 */
    free_static_list(list, j); /* 将删除节点回收到备用链表 */

    return 0;
}




/*
 * 将第i个位置的元素返回
 * pos的范围是 [1, length]
 *
 * 成功返回0
 *
 */
int
get_static_list_item(static_list_t list[], int pos, ElemType *item)
{
    int i, k;

    /* the last array index, which point to the first item */
    k = list[LISTSIZE - 1].cur;

    if (pos < 1 || pos > get_static_list_length(list))
        return -1;

    /* 找到第i个元素 */
    for (i = 1; i < pos; ++i)
        k = list[k].cur;

    memcpy(item, &list[k].data, sizeof(ElemType));

    return 0;
}



/*
 * 查找元素在表中的位置
 * 返回的位置为[1, length]，若找不到返回0
 *
 * 时间复杂度为
 */
int
find_static_list_item(static_list_t list[], ElemType *item)
{
    int k;

    k = LISTSIZE - 1;

    while (list[k].cur != 0) {
        k = list[k].cur;
        if (memcmp(&list[k].data, item, sizeof(ElemType)) == 0)
            return k;
    }

    return 0;
}



/*
 * 静态链表遍历
 */
void
trave_static_list(static_list_t list[], void (*print_info)(int n, ElemType *item))
{
    int k;

    k = LISTSIZE - 1;

    while (list[k].cur != 0) {
        k = list[k].cur;
        print_info(k, &list[k].data);
    }
}


